#include "DynamicArray.h"
#include <iostream>
#include <cmath>
#include <cstring>

DynamicArray::DynamicArray() : capacity(10), size(0), FreePtr(nullptr), ShowPtr(nullptr), Compare(nullptr),CompareBig(nullptr)
{
    this->a = new ElementType[capacity];
}

void DynamicArray::InsertTail(const ElementType &element)
{
    if (size >= capacity)
    {
        capacity *= 2;
        ElementType *newP = new ElementType[capacity];
        for (int i = 0; i < size; i++)
        {
            newP[i] = a[i];
        }
        delete[] a;
        a = newP;
    }
    a[size++] = element;
}

void DynamicArray::InsertHead(const ElementType &element)
{
    if (size >= capacity)
    {
        capacity *= 2;
        ElementType *newP = new ElementType[capacity];
        for (int i = 0; i < size; i++)
        {
            newP[i] = a[i];
        }
        delete[] a;
        a = newP;
    }
    for (int i = size; i > 0; i--)
        a[i] = a[i - 1];
    a[0] = element;
    size++;
}

void DynamicArray::InsertByIndex(const ElementType &element, int index)
{
    if (index < 0 || index > size)
    {
        std::cout << "非法的插入位置\n";
        return;
    }
    if (size >= capacity)
    {
        capacity *= 2;
        ElementType *newP = new ElementType[capacity];
        for (int i = 0; i < size; i++)
        {
            newP[i] = a[i];
        }
        delete[] a;
        a = newP;
    }
    for (int i = size; i > index; i--)
        a[i] = a[i - 1];
    a[index] = element;
    size++;
}

void DynamicArray::show()
{
    for (int i = 0; i < size; i++)
    {
        ShowPtr(a[i]);
    }
}

DynamicArray::DynamicArray(const DynamicArray &DArray)
{
    capacity = DArray.capacity;
    size = DArray.size;
    a = new ElementType[capacity];
    for (int i = 0; i < size; i++)
    {
        a[i] = DArray.a[i];
    }
    FreePtr = DArray.FreePtr;
    ShowPtr = DArray.ShowPtr;
    Compare = DArray.Compare;
    CompareBig = DArray.CompareBig;

}

DynamicArray &DynamicArray::operator=(const DynamicArray &DArray)
{
    delete[] a;
    capacity = DArray.capacity;
    size = DArray.size;
    a = new ElementType[capacity];
    for (int i = 0; i < size; i++)
    {
        a[i] = DArray.a[i];
    }
    FreePtr = DArray.FreePtr;
    ShowPtr = DArray.ShowPtr;
    Compare = DArray.Compare;
    CompareBig = DArray.CompareBig;
    return *this;
}

DynamicArray::ElementType DynamicArray::FindByIndex(int index)
{
    if (index < 0 || index > size)
    {
        std::cout << "非法的插入位置\n";
        return nullptr;
    }
    return a[index];
}

DynamicArray DynamicArray::FindElement(const ElementType &element)
{
    static DynamicArray result;

    for (int i = 0; i < size; i++)
    {
        if (Compare(a[i], element))
        {
            int num =i;
            result.InsertTail(a[i]);
        }
    }
    result.SetFreePtr(Free);
    return result;
}

void DynamicArray::RemoveByIndex(int index)
{
    if (index < 0 || index >= size)
    {
        std::cout << "不合法的数" << std::endl;
        return;
    }
    for (int i = index; i < size - 1; i++)
    {
        a[i] = a[i + 1];
    }
    size--;
}

void DynamicArray::RemoveByElement(ElementType element)
{
    for (int i = 0; i < size; i++)
    {
        if (Compare(a[i], element))
        {
            RemoveByIndex(i);
            i--;
        }
    }
}

// // void FastSort(int *a, int start, int end)
// // {
// //     if (start >= end)
// //         return;
// //     int left = start;
// //     int right = end;
// //     int temp = a[left];
// //     while (left < right)
// //     {
// //         while (a[right] > temp && left < right)
// //             right--;
// //         if (left < right)
// //             a[left++] = a[right];
// //         while (a[left] < temp && left < right)
// //             left++;
// //         if (left < right)
// //             a[right--] = a[left];
// //     }
// //     a[left] = temp;
// //     FastSort(a, start, left - 1);
// //     FastSort(a, right + 1, end);
// // }

void DynamicArray::FastSort(int start, int end, int deepth, int MaxDepth)
{
    if (start >= end)
        return;
    // 递归的深度已经超过最大深度
    if (deepth > MaxDepth)
    {
        // 改用插入排序
        InsertSort(start, end);
    }
    // 如果没有超过
    // 用快速排序
    else
    {
        // 分组
        int pos = Partition(start, end);
        // 递归
        FastSort(start, pos - 1, deepth + 1, MaxDepth);
        FastSort(pos + 1, end, deepth + 1, MaxDepth);
    }
}

void DynamicArray::InsertSort(int start, int end)
{
    for (int i = start + 1; i <= end; i++)
    {
        int j = i;
        ElementType temp = a[j];
        for (; j > start; j--)
        {
            if (Compare1(a[j - 1], temp))
                a[j] = a[j - 1];
            else
                break;
        }
        a[j] = temp;
    }
}

int DynamicArray::Partition(int start, int end)
{
    int left = start;
    int right = end;
    ElementType temp = a[left];
    while (left < right)
    {
        while (Compare1(a[right], temp) && left < right)
            right--;
        if (left < right)
            a[left++] = a[right];
        while (Compare1(temp, a[left]) && left < right)
            left++;
        if (left < right)
            a[right--] = a[left];
    }
    a[left] = temp;
    return left;
}

void DynamicArray::Sort()
{
    FastSort(0, size - 1, 0, 2 * log2(size));
}

int DynamicArray::BinarySearch(const ElementType &element)
{
    int left = 0;
    int right = size - 1;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        if (Compare1(a[mid], element))
            right = mid - 1;
        else if (Compare1(element, a[mid]))
            left = mid + 1;
        else
            return mid;
    }
    return -1;
}

// 数列有序
bool DynamicArray::IsChild(const DynamicArray &array)
{
    int count = 0;
    for (int i = 0; i < size; i++)
    {
        if (Compare(a[i], array.a[count]))
        {
            count++;
        }
    }
    return count == array.size;
}

// 滑动窗口
bool DynamicArray::IsConChild(const DynamicArray &array)
{
    for (int i = 0; i <= size - array.size; i++)
    {
        if (subsquence(i, array.size) == array)
            return true;
    }
    return false;
}

DynamicArray DynamicArray::subsquence(int index, int len)
{
    static DynamicArray sub;
    for (int i = index; i < index + len; i++)
    {
        sub.InsertTail(a[i]);
    }
    sub.SetFreePtr(Free);
    return sub;
}

void DynamicArray::UpdateByIndex(int index, const ElementType &element)
{
    // char *p = (char*)(FindByIndex(index));
    if (index < 0 || index >= size)
    {
        std::cout << "不合法的数" << std::endl;
        return;
    }
    char *p1 = (char *)element;
    // if(p)
    a[index] = p1;
}

void DynamicArray::UpdateByElement(const ElementType &oldValue, const ElementType &newValue)
{
    for (int i = 0; i < size; i++)
    {
        if (Compare(a[i], oldValue))
            a[i] = newValue;
    }
}

void DynamicArray::Duplicate()
{
    for (int i = 1; i < size; i++) // O(n)
    {
        if (Compare(a[i], a[i - 1]))
        {
            RemoveByIndex(i);
            i--;
        }
    }
}

// 归并排序：双指针 O(n)
DynamicArray DynamicArray::Merge(const DynamicArray &a)
{
    int first = 0;
    int second = 0;
    static DynamicArray result;
    // 两个数列都没到末尾
    while (first < this->size && second < a.size)
    {
        if (Compare(a.a[second], this->a[first]))
            result.InsertTail(this->a[first++]);
        else
            result.InsertTail(a.a[second++]);
    }
    while (first < this->size)
        result.InsertTail(this->a[first++]);
    while (second < a.size)
        result.InsertTail(a.a[second++]);
    result.SetFreePtr(Free);
    return result;
}

// 两个数列有序
DynamicArray DynamicArray::FindInterSection(const DynamicArray &array)
{
    int first = 0;
    int second = 0;
    static DynamicArray result;
    while (first < size && second < array.size)
    {
        if (Compare(a[first] , array.a[second]))
        {
            result.InsertTail(a[first]);
            first++;
            second++;
        }
        else if (Compare1(array.a[second] ,a[first]))
            first++;
        else
            second++;
    }
    result.SetFreePtr(Free);
    return result;
}

DynamicArray DynamicArray::FindUnionSet(const DynamicArray &array)
{
    int first = 0;
    int second = 0;
    static DynamicArray result;
    while (first < size && second < array.size)
    {
        if (Compare(a[first] , array.a[second]))
        {
            result.InsertTail(a[first]);
            first++;
            second++;
        }
        else if (Compare1(array.a[second],a[first]) )
            result.InsertTail(a[first++]);
        else
            result.InsertTail(array.a[second++]);
    }
    while (first < this->size)
        result.InsertTail(this->a[first++]);
    while (second < array.size)
        result.InsertTail(array.a[second++]);
    result.SetFreePtr(Free);
    return result;
}

DynamicArray DynamicArray::FindDifference(const DynamicArray &array)
{
    int first = 0;
    int second = 0;
    static DynamicArray result;
    while (first < size && second < array.size)
    {
        if (Compare( a[first] , array.a[second]))
        {
            first++;
            second++;
        }
        else if (Compare1( array.a[second],a[first]))
            result.InsertTail(a[first++]);
        else
            result.InsertTail(array.a[second++]);
    }
    while (first < this->size)
        result.InsertTail(this->a[first++]);
    while (second < array.size)
        result.InsertTail(array.a[second++]);
    result.SetFreePtr(Free);
    return result;
}

bool DynamicArray::operator==(const DynamicArray &array)
{
    if (size != array.size)
        return false;
    int index = 0;
    while (index < size)
    {
        if (Compare(a[index], array.a[index]) == 0)
            return false;
        index++;
    }
    return true;
}

void Free(DynamicArray::ElementType element)
{
    int *p = (int *)element;
    delete[] p;
}

void Show(DynamicArray::ElementType element)
{
    std::string *p = (std::string *)element;
    std::cout << *p << std::endl;
}

void ShowChar(DynamicArray::ElementType element)
{
    char *p = (char *)element;
    std::cout << p << std::endl;
}

void ShowInt(DynamicArray::ElementType element)
{
    int *p = (int *)element;
    for (int i = 0; i < 3; i++)
        std::cout << p[i] << " ";
    std::cout << std::endl;
}

void ShowIntNum(DynamicArray::ElementType element)
{
    int *p = (int *)element;
    std::cout << *p << std::endl;
}

bool Compare(DynamicArray::ElementType ptr, DynamicArray::ElementType str)
{
    const char *p1 = (const char *)ptr;
    const char *p2 = (const char *)str;
    return strcmp(p1, p2) == 0;
}

bool Compare1(DynamicArray::ElementType ptr, DynamicArray::ElementType str)
{
    const char *p1 = (const char *)ptr;
    const char *p2 = (const char *)str;
    return strcmp(p1, p2) > 0;
}

DynamicArray::~DynamicArray()
{
    if(FreePtr)
    FreePtr(a);
    delete []a;
}
